39. 组合总和

// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的数字可以无限制重复被选取。
// 说明：
// 所有数字（包括 target）都是正整数。
// 解集不能包含重复的组合。
var combinationSum = function(candidates, target) {
  if (candidates.length === 0) return [];
  candidates = candidates.sort((a, b) => a - b);
  const totalArr = [];

  function dfs(arr, res, start) {
    for (let i = start; i < candidates.length; i++) {
      const sum = res + candidates[i];
      if (sum === target) {
        totalArr.push([...arr, candidates[i]]);
        break;
      } else if (sum > target) {
        break;
      } else {
        dfs([...arr, candidates[i]], sum, i);
      }
    }
  }

  dfs([], 0, 0);

  return totalArr;
};
// console.log(combinationSum([2, 3, 6, 7], 7));
// console.log(combinationSum([2, 3, 5], 8));
console.log(combinationSum([2, 7, 6, 3, 5, 1], 9));